import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.*;

class AStarCompare implements Comparator<Board>{
	public AStarCompare(){
		
	}
	public int compare(Board a,Board b){
		if(a.equals(b)){
			return 0;
		}
		int test=a.heuristic()-b.heuristic();
		if(test!=0){
			return test;
		}
		else{
			return -1;
		}
		/*else{
			if(b.size!=a.size){
				return a.size-b.size;
			}
			for(int i=0;i<a.size;i++){
				for(int j=0;j<b.size;j++){
					if(a.board[i][j]!=b.board[i][j]){
						return a.board[i][j]-b.board[i][j];
					}
				}
			}
			return 0;
		}*/
	}
}
public class Board implements Comparable<Board>{
	int[][] board;
	int emptyRow;
	int emptyColumn;
	int size;
	int steps;
	int score=-1;
	int pos_pairs=-1;
	int neg_pairs=-1;
	double regress=-1;
	public Board(int size){
		this.size=size;
		this.board=new int[size][size];
		int cur=1;
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				this.board[i][j]=cur;
				cur++;
			}
		}
		this.board[size-1][size-1]=-1;
		this.emptyRow=size-1;
		this.emptyColumn=size-1;
		this.steps=0;
	}
	public Board(int[][] board,int emptyRow,int emptyColumn,int size,int steps){
		this.board=new int[size][size];
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				this.board[i][j]=board[i][j];
			}
		}
		this.emptyRow=emptyRow;
		this.emptyColumn=emptyColumn;
		this.size=size;
		this.steps=steps;
	}
	public int getSize(){
		return size;
	}
	
	//0 is UP
	//1 is RIGHT
	//2 is DOWN
	//3 is LEFT
	public Board[] neighbors(){
		Board[] neighborList=new Board[4];
		int i=0;
		for(int move_num=0;move_num<4;move_num++){
			Board b=new Board(this.board,this.emptyRow,this.emptyColumn,this.size,this.steps);
			if(b.move(move_num)>0){
				neighborList[i]=b;
				i++;
			}
		}
		Board[] trueNeighbors=new Board[i];
		for(int j=0;j<trueNeighbors.length;j++){
			trueNeighbors[j]=neighborList[j];
		}
		return trueNeighbors;
	}
	public int move(int dir){
		if(dir==0 && emptyRow!=0){
			int temp=board[emptyRow-1][emptyColumn];
			board[emptyRow-1][emptyColumn]=-1;
			board[emptyRow][emptyColumn]=temp;
			emptyRow--;
			this.steps++;
			this.score=-1;
			this.pairs();
			this.score=this.heuristic();
			return 1;
		}
		if(dir==1 && emptyColumn!=size-1){
			int temp=board[emptyRow][emptyColumn+1];
			board[emptyRow][emptyColumn+1]=-1;
			board[emptyRow][emptyColumn]=temp;
			emptyColumn++;
			this.steps++;
			this.score=-1;
			this.pos_pairs=-1;
			this.neg_pairs=-1;
			this.pairs();
			this.score=this.heuristic();
			return 1;
		}
		if(dir==2 && emptyRow!=size-1){
			int temp=board[emptyRow+1][emptyColumn];
			board[emptyRow+1][emptyColumn]=-1;
			board[emptyRow][emptyColumn]=temp;
			emptyRow++;
			this.steps++;
			this.score=-1;
			this.pos_pairs=-1;
			this.neg_pairs=-1;
			this.score=this.heuristic();
			return 1;
		}
		if(dir==3 && emptyColumn!=0){
			int temp=board[emptyRow][emptyColumn-1];
			board[emptyRow][emptyColumn-1]=-1;
			board[emptyRow][emptyColumn]=temp;
			emptyColumn--;
			this.steps++;
			this.score=-1;
			this.score=this.heuristic();
			return 1;
		}
		return -1;
	}
	public int manhattan(int i, int j){
		int number=board[i][j];
		if(number==-1){
			number=this.size*this.size;
		}
		int trueRow=(int)Math.ceil(((double)number)/((double)size));
		int trueCol=number % size;
		if(trueCol==0){
			trueCol=size;
		}
		return (Math.abs(i-(trueRow-1))+Math.abs(j-(trueCol-1)));
	}
	public void pairs(){
		if(this.pos_pairs!=-1 || this.neg_pairs!=-1){
			return;
		}
		this.pos_pairs=0;
		this.neg_pairs=0;
		for(int i=0;i<this.size;i++){
			for(int j=0;j<this.size;j++){
				int cur_num=board[i][j];
				if(cur_num==-1){
					cur_num=this.size*this.size;
				}
				if(j!=this.size-1){
					int right_num=board[i][j+1];
					if(right_num==-1){
						right_num=this.size*this.size;
					}
					if(right_num==cur_num+1){
						this.pos_pairs++;
					}
					if(right_num==cur_num-1){
						this.neg_pairs++;
					}
				}
				if(i!=this.size-1){
					int down_num=board[i+1][j];
					if(down_num==-1){
						down_num=this.size*this.size;
					}
					if(down_num==cur_num+this.size){
						this.pos_pairs++;
					}
					if(down_num==cur_num-this.size){
						this.neg_pairs++;
					}
				}
			}
		}
	}
	public int correct_positions(){
		int cur=1;
		int positions=0;
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				if(this.board[i][j]==cur){
					positions++;
				}
				cur++;
			}
		}
		return positions;
	}
	public int correct_rows(){
		int cur=1;
		int rows=0;
		for(int i=0;i<size;i++){
			boolean rowCorrect=true;
			for(int j=0;j<size;j++){
				if(cur==9){
					cur=-1;
				}
				if(this.board[i][j]!=cur){
					rowCorrect=false;
				}
				cur++;
			}
			if(rowCorrect){
				rows++;
			}
		}
		return rows;
		
	}
	public int correct_cols(){
		int cur=1;
		int cols=0;
		boolean colCorrect[]=new boolean[this.size];
		for(int i=0;i<size;i++){
			colCorrect[i]=true;
		}
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				if(this.board[i][j]!=cur){
					colCorrect[j]=false;
				}
				cur++;
			}
		}
		for(int i=0;i<size;i++){
			if(colCorrect[i]){
				cols++;
			}
		}
		return cols;
		
	}
	public double euclidian(int i, int j){
		int number=board[i][j];
		if(number==-1){
			number=this.size*this.size;
		}
		int trueRow=(int)Math.ceil(((double)number)/((double)size));
		int trueCol=number % size;
		if(trueCol==0){
			trueCol=size;
		}
		//double normalize=Math.sqrt((this.size-1)^2+(this.size-1)^2);
		return Math.sqrt(Math.abs(i-(trueRow-1))*Math.abs(i-(trueRow-1))+Math.abs(j-(trueCol-1))*Math.abs(j-(trueCol-1)))/Math.sqrt(Math.abs(this.size-1)*Math.abs(this.size-1)+Math.abs(this.size-1)*Math.abs(this.size-1));
		
	}
	public int heuristic(){
		if(this.score!=-1){
			return this.score;
		}
		int s=0;
		for(int i=0;i<this.size;i++){
			for(int j=0;j<this.size;j++){
				s=s+this.manhattan(i, j);
			}
		}
		this.score=s;
		return s;
	}
	public int compareTo(Board b){
		return this.steps-b.steps;
	}
	public String prettyPrint(){
		String out="";
		if(this.regress!=-1){
			out="Regression: "+this.regress+"\n";
		}
		//out=this.steps+" steps:\n";
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				if(board[i][j]<10 && board[i][j]>0){
					out=out+' '+' '+String.valueOf(board[i][j]);
				}
				else{
					out=out+' '+String.valueOf(board[i][j]);
				}
			}
			out=out+"         ";
			for(int j=0;j<size;j++){
				int m=this.manhattan(i,j);
				if(m<10){
					out=out+' '+' '+String.valueOf(m);
				}
				else{
					out=out+' '+String.valueOf(m);
				}
			}

			out=out+"         ";
			for(int j=0;j<size;j++){
				double m=this.euclidian(i,j);
				if(m<10){
					out=out+' '+' '+String.format("%.2g", m);
				}
				else{
					out=out+' '+String.format("%.2g", m);
				}
			}
			out=out+'\n';
		}
		return out;
		
	}
	public String printBoard(){
		String out="";
		out=out+this.steps;
		int index = 0;
		int newSize = size*size;
		double[] vector = new double[newSize];
		double[] vector_euclidian = new double[newSize];
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				//out=out+','+String.valueOf(board[i][j])+','+String.valueOf(manhattan(i,j));
				index = board[i][j];
				if (index == -1){
					index = 9;
				}
				vector[index-1] = manhattan(i,j);
				
			}
		}
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				//out=out+','+String.valueOf(board[i][j])+','+String.valueOf(manhattan(i,j));
				index = board[i][j];
				if (index == -1){
					index = 9;
				}
				vector_euclidian[index-1] = euclidian(i,j);
			}
		}
		int var_index=1;
		for(int k=0; k<newSize; k++){
			out=out + " "+var_index+":"+String.valueOf(vector[k]/(Math.abs(this.size-1)+Math.abs(this.size-1)))+" "+(var_index+1)+":"+String.valueOf(vector_euclidian[k]);
			var_index=var_index+2;
		}
		this.pairs();
		double pairs_norm=this.size*((this.size-1)*2);
		out=out+' '+var_index+":"+this.pos_pairs/pairs_norm+' '+(var_index+1)+":"+this.neg_pairs/pairs_norm;
		var_index=var_index+2;
		out=out+' '+var_index+":"+(double)this.correct_positions()/(this.size*this.size);
		var_index++;
		out=out+' '+var_index+":"+(double)this.correct_rows()/this.size;
		var_index++;
		out=out+' '+var_index+":"+(double)this.correct_cols()/this.size;
		var_index++;
		return out;
		//return out;
	}
	public static String writeHeader(int len, int lookback,int max_steps,int size){
		String out="@RELATION Boards";
		out=out+Integer.valueOf(len)+"_"+Integer.valueOf(lookback)+"_";
		out=out+Integer.valueOf(max_steps)+"_"+Integer.valueOf(size)+"\r\n";
		/*for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				out=out+"@ATTRIBUTE loc_"+Integer.valueOf(i)+"_"+Integer.valueOf(j)+"\t{";
				out=out+"-1";
				for(int k=1;k<size*size;k++){
					out=out+","+Integer.valueOf(k);
				}
				out=out+"}\r\n";
				out=out+"@ATTRIBUTE manhattan_"+Integer.valueOf(i)+"_"+Integer.valueOf(j)+"\t{";
				out=out+"0";
				for(int k=1;k<size*2+1;k++){
					out=out+","+Integer.valueOf(k);
				}
				out=out+"}\r\n";
			}
		}
		out=out+"@ATTRIBUTE steps\tNUMERIC\r\n";
		out=out+"@DATA\r\n";*/
		for(int i=0;i<size;i++){
			for(int j=0;j<size;j++){
				out=out+"@ATTRIBUTE manhattan_"+Integer.valueOf(i)+"_"+Integer.valueOf(j)+"\tNUMERIC\r\n";
				out=out+"@ATTRIBUTE euclidian_"+Integer.valueOf(i)+"_"+Integer.valueOf(j)+"\tNUMERIC\r\n";
			}
		}
		/*out=out+','+this.pos_pairs/pairs_norm+','+this.neg_pairs/pairs_norm;
		out=out+','+(double)this.correct_positions()/(this.size*this.size);
		out=out+','+(double)this.correct_rows()/this.size;
		out=out+','+(double)this.correct_cols()/this.size;*/
		out=out+"@ATTRIBUTE cor_pairs\tNUMERIC\r\n";
		out=out+"@ATTRIBUTE wrong_pairs\tNUMERIC\r\n";
		out=out+"@ATTRIBUTE cor_positions\tNUMERIC\r\n";
		out=out+"@ATTRIBUTE cor_rows\tNUMERIC\r\n";
		out=out+"@ATTRIBUTE cor_cols\tNUMERIC\r\n";
		out=out+"@ATTRIBUTE steps\tNUMERIC\r\n";
		out=out+"@DATA\r\n";
		return out;
		
	}
	public static Board[] permuteBoards(int len, int lookback,int max_steps,int size){
		PriorityQueue<Board> previous=new PriorityQueue<Board>();
		previous.add(new Board(size));
		Board[] output=new Board[len];
		int curOutputSize=0;
		Random r=new Random();
		Board currentBoard=new Board(size);
		int curStep=0;
		while(curOutputSize<len){
			int nextRand=r.nextInt(4);
			if(currentBoard.move(nextRand)<0){
				continue;
			}
			curStep++;
			if(curStep>max_steps){
				curStep=0;
				currentBoard=new Board(size);
				continue;
			}
			//System.out.println("Checking Boards");
			boolean found=false;
			Iterator<Board> i=previous.iterator();
			while(i.hasNext()){
				Board b=i.next();
				if(Board.equals(currentBoard, b)){
					//System.out.println("found");
					if(b.steps<curStep){
						curStep=b.steps;
					}
					if(curStep<b.steps){
						b.steps=curStep;
					}
					found=true;
				}
			}
			if(found==false){
				/*Board[]	path=Board.aStar(currentBoard);
				if(path.length<curStep){
					System.out.println(path.length);
					curStep=path.length;
				}*/
				/*for(int i=0;i<lookback-1;i++){
					previous[i]=previous[i+1];
				}*/
				if(previous.size()==lookback){
					previous.poll();
				}
				previous.add(new Board(currentBoard.board,currentBoard.emptyRow,currentBoard.emptyColumn,currentBoard.size,curStep));
				//System.out.println(previous.size());
				//previous[lookback-1]=new Board(currentBoard.board,currentBoard.emptyRow,currentBoard.emptyColumn,currentBoard.size,curStep);
				output[curOutputSize]=new Board(currentBoard.board,currentBoard.emptyRow,currentBoard.emptyColumn,currentBoard.size,curStep);
				curOutputSize++;
				
			}
		}
		return output;
	}
	public static boolean equals(Board currentBoard, Board board2) {
		if(board2.size!=currentBoard.size){
			return false;
		}
		for(int i=0;i<currentBoard.size;i++){
			for(int j=0;j<currentBoard.size;j++){
				if(currentBoard.board[i][j]!=board2.board[i][j]){
					//System.out.println("Returning False");
					return false;
				}
			}
		}
		//System.out.println("Returning True");
		return true;
	}
	public boolean equals(Board board2) {
		if(board2.size!=this.size){
			return false;
		}
		for(int i=0;i<this.size;i++){
			for(int j=0;j<this.size;j++){
				//System.out.println("boards are equal");
				if(this.board[i][j]!=board2.board[i][j]){
					//System.out.println("boards not equal");
					return false;
				}
			}
		}
		return true;
	}
	public void setBoard(int[][] b,int row,int col){
		board=b;
	}
	public static Board[] concat(Board[] A, Board[] B) {
		   Board[] C= new Board[A.length+B.length];
		   System.arraycopy(A, 0, C, 0, A.length);
		   System.arraycopy(B, 0, C, A.length, B.length);

		   return C;
		}
	public static Board[] search(Board node, int depth,String fileName,HashMap<Board,Board> parents){
		Board[] neighborList=node.neighbors();
		for(int i=0;i<neighborList.length;i++){
			parents.put(neighborList[i], node);
		}
		if(depth==1){
			try{
				FileWriter fstream = new FileWriter(fileName,true);
				BufferedWriter outFile = new BufferedWriter(fstream);
				//outFile.write(Board.writeHeader(len,lookback,maxSteps,size));
				for(int i=0;i<neighborList.length;i++){
					outFile.write(neighborList[i].printBoard());
					outFile.newLine();
				}
				outFile.close();
			}
			catch (Exception e){//Catch exception if any
				System.err.println("cant write to file");
				System.err.println("Error: " + e.getMessage());
			}
			return neighborList;
		}
		else{
			Board[] l=new Board[0];
			for(int i=0;i<neighborList.length;i++){
				l=Board.concat(search(neighborList[i],depth-1,fileName,parents),l);
			}
			return l;
		}
	}
	public void set_regression(double val){
		this.regress=val;
	}
	public static Board[] smallest_Boards(String fileName,int num_boards,Board[] origList){
		Board[] returnBoards=new Board[num_boards];
		BufferedReader inFile;
		int index=0;
		double[] values=new double[num_boards];
		for(int i=0;i<num_boards;i++){
			values[i]=0;
		}
		int[] indicies=new int[num_boards];
		for(int i=0;i<num_boards;i++){
			indicies[i]=0;
		}
		try{
			FileReader fstream = new FileReader(fileName);
			inFile = new BufferedReader(fstream);
			String line=inFile.readLine();
			for(int i=0;i<num_boards;i++){
				double val=Double.valueOf(line).doubleValue();
				origList[index].set_regression(val);
				values[i]=val;
				indicies[i]=index;
				index++;
				line=inFile.readLine();
			}
			while(line!=null){
				double val=Double.valueOf(line).doubleValue();
				//System.out.println(val);
				origList[index].set_regression(val);
				for(int i=0;i<num_boards;i++){
					if(val<values[i]){
						boolean found=false;
						for(int j=0;j<num_boards;j++){
							if(origList[indicies[j]].equals(origList[index])){
								found=true;
								break;
							}
						}
						if(found==false){
							values[i]=val;
							indicies[i]=index;
							break;
						}
						
					}
				}
				line=inFile.readLine();
				index++;
			}
			inFile.close();
		}
		catch (Exception e){//Catch exception if any
			System.err.println("cant read from file");
			System.err.println("Error: " + e.getMessage());
		}
		finally{
			for(int i=0;i<num_boards;i++){
				returnBoards[i]=origList[indicies[i]];
			}
			
		}
		return returnBoards;
	}
	/*public static Board[] aStar(Board start){
		Board goal=new Board(start.getSize());
		TreeSet<Board> opened=new TreeSet<Board>(new AStarCompare());
		TreeSet<Board> closed=new TreeSet<Board>(new AStarCompare());
		opened.add(start);
		HashMap<Board,Integer> g_score=new HashMap<Board,Integer>();
		HashMap<Board,Integer> f_score=new HashMap<Board,Integer>();
		HashMap<Board,Board> came_from=new HashMap<Board,Board>();
		g_score.put(start,new Integer(0));
		f_score.put(start,start.heuristic());
		while(opened.size()!=0){
			Board x=opened.first();
			if(x.equals(goal)){
				return Board.reconstructPath(x,came_from);
			}
			opened.remove(x);
			closed.add(x);
			Board[] neighborList=x.neighbors();
			int tentative_g_score=g_score.get(x).intValue()+1;
			for(int i=0;i<neighborList.length;i++){
				Board y=neighborList[i];
				if(opened.contains(y)==false && closed.contains(y)==false){
					opened.add(y);
					came_from.put(y,x);
					g_score.put(y,tentative_g_score);
					f_score.put(y,g_score.get(y)+y.heuristic());
				}
				else{
					if(tentative_g_score<g_score.get(y).intValue()){
						came_from.put(y,x);
						g_score.put(y,tentative_g_score);
						f_score.put(y,g_score.get(y)+y.heuristic());
					}
				}
			}
			for(int i=0;i<neighborList.length;i++){
				Board y=neighborList[i];
				if(closed.contains(y)){
					continue;
				}
				int tentative_g_score=g_score.get(x).intValue()+1;
				if(opened.contains(y)==false){
					opened.add(y);
					came_from.put(y,x);
					g_score.put(y,tentative_g_score);
					f_score.put(y,g_score.get(y)+y.heuristic());
					continue;
				}
				else if(tentative_g_score<g_score.get(y).intValue()){
					came_from.put(y,x);
					g_score.put(y,tentative_g_score);
					f_score.put(y,g_score.get(y)+y.heuristic());
					continue;
				}
				if(!opened.contains(y)){
					opened.add(y);
					tentative_is_better=true;
				}
				else if(tentative_g_score<g_score.get(y).intValue()){
					tentative_is_better=true;
				}
				if(tentative_is_better){
					came_from.put(y,x);
					g_score.put(y,tentative_g_score);
					f_score.put(y,g_score.get(y)+y.heuristic());
				}
			}
		}
		return new Board[0];
	}*/
	public static Board[] reconstructPath(Board node,HashMap<Board,Board> came_from){
		if(came_from.containsKey(node)){
			Board[] p=reconstructPath(came_from.get(node),came_from);
			Board[] ret=new Board[p.length+1];
			for(int i=0;i<p.length;i++){
				ret[i]=p[i];
			}
			ret[p.length]=node;
			return ret;
		}
		else{
			Board[] ret=new Board[1];
			ret[0]=node;
			return ret;
		}
	}
	public static Board[] path(Board start,Board end,HashMap<Board,Board> parents){
		Board[] list=new Board[1];
		list[0]=start;
		Board b=parents.get(start);
		while(b!=null){
			Board[] temp=new Board[1];
			temp[0]=b;
			list=Board.concat(list,temp);
			b=parents.get(b);
		}
		return Board.reverse(list);
	}
	public static Board[] reverse(Board[] list){
		Board[] rev=new Board[list.length];
		for(int i=0;i<list.length;i++){
			rev[list.length-1-i]=list[i];
		}
		return rev;
	}
	public static Board[] solve(Board start){
		HashMap<Board,Board> parents=new HashMap<Board,Board>();
	    //System.out.println("Input Board:\n"+start.prettyPrint());
		String fileName="out.txt";
		int num_kept=5;
		int depth=3;
		Board[] results=Board.regressionSearch(start,depth,num_kept,fileName,parents);
		Board goal=new Board(start.size);
		for(int i=0;i<num_kept;i++){
			if(results[i].equals(goal)){
				return Board.path(results[i],start,parents);
			}
		}
		Board[][] paths=new Board[num_kept][];
		for(int i=0;i<num_kept;i++){
			Board[] list=Board.solve(results[i]);
			paths[i]=Board.concat(Board.path(results[i],start , parents),list);
		}
		int min=paths[0].length;
		int min_index=0;
		for(int i=1;i<num_kept;i++){
			if(paths[i].length<min){
				min=paths[i].length;
				min_index=i;
			}
		}
		return paths[min_index];
		
	}
	public static Board[] regressionSearch(Board start,int depth,int num_kept,String fileName,HashMap<Board,Board> parents){
	    File f = new File(fileName);
	    f.delete();
		Board[] boards=Board.search(start,depth,fileName,parents);
		Board[] newBoards;
		try{
			Process p=Runtime.getRuntime().exec("./svm_classify.exe "+fileName+" 8PuzzleModel results.txt");
			p.waitFor();
			newBoards=Board.smallest_Boards("results.txt",num_kept,boards);
			return newBoards;
		}
		catch (Exception e){//Catch exception if any
			System.err.println("Error: " + e.getMessage());
		}
		return null;

	}
	public static void main(String[] args){
		//Board b=new Board(5);
		//System.out.println(b.prettyPrint());
		int size=3;
		int len=2680;
		int lookback=5;
		int maxSteps=3;
		Board[] out=Board.permuteBoards(len,lookback,maxSteps,size);
		/*try{
			// Create file
			String fileName="Boards_";
			fileName=fileName+Integer.valueOf(len)+"_"+Integer.valueOf(lookback)+"_";
			fileName=fileName+Integer.valueOf(maxSteps)+"_"+Integer.valueOf(size)+".txt";
			FileWriter fstream = new FileWriter(fileName);
			BufferedWriter outFile = new BufferedWriter(fstream);
			//outFile.write(Board.writeHeader(len,lookback,maxSteps,size));
			for(int i=0;i<len;i++){
				System.out.println(out[i].printBoard());
				System.out.println(out[i].prettyPrint());
				outFile.write(out[i].printBoard());
				outFile.newLine();
			}
			//Close the output stream
			outFile.close();
		}
		catch (Exception e){//Catch exception if any
			System.err.println("Error: " + e.getMessage());
		}*/
		HashMap<Board,Board> parents=new HashMap<Board,Board>();
	    System.out.println("Input Board:\n"+out[25].prettyPrint());
		String fileName="out.txt";
		int num_kept=5;
		int depth=3;
		//Board[] results=Board.regressionSearch(out[25],depth,num_kept,fileName,parents);
		Board[] results=Board.solve(out[25]);
		
		for(int i=0;i<results.length;i++){
			System.out.println(results[i].prettyPrint());
			/*Board b=parents.get(results[i]);
			System.out.println("Parents:");
			while(b!=null){
				System.out.println(b.prettyPrint());
				b=parents.get(b);
			}*/
		}
		
	}
}